package org.example.algorithm.array;

public class FindMedianSortedArraysSolution {

    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        FindMedianSortedArraysSolution solution = new FindMedianSortedArraysSolution();
        double ans = solution.findMedianSortedArrays(nums1, nums2);
        System.out.println(ans);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int leftNum = (len1 + len2 + 1) / 2;
        int left = 0;
        int right = len1;
        while (left < right) {
            //避免left = i造成死循环
            int i = (left + right + 1) >> 1;
            int j = leftNum - i;
            if (nums1[i-1] > nums2[j]) {
                right = i-1;
            } else {
                //这里收缩的依据是？
                left = i;
            }
        }
        int pos1 = left;
        int pos2 = leftNum - left;
        int nums1Left = pos1 >= 1 ? nums1[pos1-1] : Integer.MIN_VALUE;
        int nums1Right = pos1 < len1 ? nums1[pos1] : Integer.MAX_VALUE;
        int nums2Left =  pos2>= 1 ? nums2[pos2-1] : Integer.MIN_VALUE;
        int nums2Right = pos2 < len2 ? nums2[pos2] : Integer.MAX_VALUE;
        if ((len1 + len2) % 2 == 0) {
            return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2.0;
        } else {
            return Math.max(nums1Left, nums2Left);

        }
    }
}
